package 回溯;

import java.util.*;

/**
 * @author aodre , QQ : 480029069
 * @date 2022/12/16 10:11
 */
public class leetcode140单词拆分 {

    private Set<String> hs;
    private List<String> res;
    /*
      0 ms
      而且 直接 用的 StringBuilder
      ，问题在于

     */
    private void bt(int st,int e,String s,StringBuilder sent){
        if(e==s.length()){
            if(e-st ==0) res.add(sent.toString());
        }else{

            bt(st,e+1,s,sent);
            String sub = s.substring(st,e+1);
            if(hs.contains(sub)){
                int be = sent.length();
                if(sent.length() != 0) sent.append(" ");
                sent.append(sub);
                int end = sent.length();
                bt(e+1,e+1,s,sent);
                sent.delete(be,end);
            }
        }
    }



    /*
     题倒是 没什么 难度， 主要是这样 对 格式有要求的 这种 回溯
     更推荐， 先收集完成， 再同一 处理格式， 比如 添加 “ . ”  空格
     逗号 , ** 等等 这些格式要求
     */
    // 2023/2/1 更新 AC
    public void recursionNew(int index,String s,Set<String> set,Deque<String> path,List<String> ans){
        if(index == s.length()){
            ans.add(String.join(" ",path));
        }
        for(int i = index + 1;i <= s.length();i++){
            String temp = s.substring(index,i);
            if(set.contains(temp)){
                path.addLast(temp);
                recursionNew(i,s,set,path,ans);
                path.removeLast();
            }
        }
    }

    /*
        写后感 ：
        一定要审题：， 注意题目要求的输出格式是什么
        收获：
        对于该题来说，
        ①你可以 在 收集 单词的 时候 就处理格式 ， 这里的格式是指 单词 间的 空格 ，边收集 便处理 ，其实比较繁琐
        ②： 也可以在 最后添加 结果的 时候 统一处理 格式 ， 这种是比较推荐的方式！
        像这种题 使用 这种        栈式 Deque 的 数据结构要必
        使用 StringBuilder 方便 一些

     */
    public static List<String> solution(String s,List<String> wordDict){
        int len = wordDict.size();
        int sLen = s.length();
        Set<String>  dict = new HashSet<>(len);
        for(String str : wordDict)
            dict.add(str);
        Deque<String> path = new ArrayDeque<>();

        List<String> ans = new ArrayList<>();
        recursion(0,s,dict,path,ans,sLen);
        return ans;
    }
    public static void recursion(int index, String s, Set<String> dict,Deque<String> path, List<String> ans,int len){
        if(index == len){
            /*
            StringBuilder temp = new StringBuilder();
            for(String str : path)
                temp.append(str + " ");
            ans.add(temp.toString().trim());
            */
         ans.add(String.join(" ",path));
        }

        for(int i = index + 1;i <= len; i++){
            String substring = s.substring(index, i);
            if(dict.contains(substring)){
                path.addLast(substring);
                recursion(i,s,dict,path,ans,len);
                path.removeLast();
            }
        }

    }

    public static void main(String[] args) {
        String s = "catsanddog";
        List<String> dict = Arrays.asList("cat","cats","and","sand","dog");
        System.out.println(solution(s,dict));
    }

}
/*
另外一种 递归的 方式
这种思考的方式，可以运用到工程上面去的
 */
class Solution {
    List<String> res = new ArrayList<>();
    public List<String> wordBreak(String s, List<String> wordDict) {
        dfs(s, 0, new StringBuilder(), wordDict);
        return res;
    }
    public void dfs(String s, int index, StringBuilder sb, List<String> wordDict){
        if(index == s.length()){
            res.add(sb.toString().substring(0, sb.length()-1));
            return;
        }
        for(int i = 0;i < wordDict.size();i++){
            String tmp = wordDict.get(i);
            if(s.substring(index, Math.min(s.length(), index + tmp.length())).equals(tmp))  {
                sb.append(tmp);
                sb.append(' ');
                dfs(s, index + tmp.length(), sb, wordDict);
                sb.delete(sb.length()-tmp.length()-1, sb.length());
            }
        }
    }
}